#include <bits/stdc++.h>

using namespace std;
using P = pair<int, int>;
// 定义P为pair<int, int>的别名，用于存储边

/**
 * 主函数
 * 功能：求解图的最小割问题，将图的顶点分成两组，使得连接两组的边数最少
 */
int main() {
  int n, m;      // n: 顶点数量，m: 边的数量
  cin >> n >> m; // 从标准输入读取顶点数和边数

  vector<P> edge; // 存储图中所有的边
  // 读取m条边的信息
  for (int i = 0; i < m; ++i) {
    int u, v;      // 边的两个顶点
    cin >> u >> v; // 读取边的顶点编号
    --u;
    --v;                     // 将顶点编号从1-based转换为0-based
    edge.emplace_back(u, v); // 将边添加到edge向量中
  }

  // 初始化答案为最大可能值（所有边都在割集中的情况）
  int ans = m;

  // 枚举所有可能的顶点划分方式（使用位掩码s表示）
  // 1<<n 表示2^n种可能的划分方式
  for (int s = 0; s < (1 << n); ++s) {

    // 计算当前划分下不处于割集中的边数
    int now = 0;
    // 遍历所有边
    for (auto [u, v] : edge) {
      // 如果边的两个顶点属于同一组，则这条边不是割边
      int color_u = s >> u & 1;
      int color_v = s >> v & 1;
      if (color_u == color_v) {
        now++;
      }
    }

    // 更新最小割边数（总边数减去不处于割集的边数等于割边数）
    ans = min(ans, now);
  }

  // 输出最小割边数
  cout << ans << '\n';

  return 0;
}